package regEx;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

import regEx.dfa.DFA;
import regEx.dfa.DFAState;
import regEx.finiteAutomata.NFA;
import regEx.finiteAutomata.State;
import ast.ASTNode;
import ast.nodes.RegExNode;

public class RegExEvaluator {

    /** Graph for the NFA */
    private NFA nfa;

    private DFA dfa;

    /** an ID counter variable used to keep track of the states in a NFA/DFA */
    private int nextId;

    public RegExEvaluator() {
        nextId = 0;
    }

    /**
     * Gets the ID for the next state.
     * @return
     */
    private int getID() {
        return nextId++;
    }

    /**
     * Returns the NFA associated with the RegEx.
     *
     * If the NFA hasnt been created, then this function will take an AST and convert it to an NFA
     * @param regExAST the AST representing the regular expression
     * @return the NFA associated with this regExNode.
     * @throws Exception if the regEx is invalid
     */
    public NFA getNFA(RegExNode regExAST) throws Exception {
        // If we already made the NFA, then get it.
        if (this.nfa != null) {
            return this.nfa;
        }

        this.nfa = new NFA();

        this.nextId = 0;
        this.nfa = this.createNFA(regExAST.getChildren().get(0));

        // Set the number of states for the NFA
        this.nfa.setNumStates(this.nextId);
        this.nfa.getEndState().setAcceptState(true);

        return this.nfa;
    }

    private NFA createNFA(ASTNode node) throws Exception {
        NFA subNFA = new NFA();
        switch (node.getData().getType()) {
        case STAR:
            subNFA = this.evalStar(node);
            break;
        case PIPE:
            subNFA = this.evalUnion(node);
            break;
        case CONCAT:
            subNFA = this.evalConcat(node);
            break;
        case PLUS:
            subNFA = this.evalPlus(node);
            break;
        case QUESTION_MARK:
            subNFA = this.evalQuestion(node);
            break;
        case CHARACTER:
            subNFA = this.evalChar(node);
            break;
        default:
            throw new Exception("Invalid Regular Expression");
        }

        return subNFA;
    }

    private NFA evalChar(ASTNode node) {
        State startState = new State(this.getID());

        State endState = new State(this.getID());

        startState.addTransition(node.getData().getTokenString().charAt(0), endState);

        NFA charNFA = new NFA(startState, endState);

        return charNFA;
    }

    private NFA evalQuestion(ASTNode node) throws Exception {

        // Create the rNFA (the NFA that is going to be 'stared'
        NFA rNFA = this.createNFA(node.getChildren().get(0));

        // Create a start state and epsilon transition to rNFA_Start
        State startState = new State(this.getID());
        startState.addTransition('e', rNFA.getStartState());

        // Create an End state and epsilon transition from rNFA_End to this end state
        State endState = new State(this.getID());
        rNFA.getEndState().addTransition('e', endState);

        // Epsilon Transition from this start to this end
        startState.addTransition('e', endState);

        NFA questionNFA = new NFA(startState, endState);

        return questionNFA;
    }

    private NFA evalPlus(ASTNode node) throws Exception {
        // Create the rNFA (the NFA that is going to be 'stared'
        NFA rNFA = this.createNFA(node.getChildren().get(0));

        // Create a start state and epsilon transition to rNFA_Start
        State startState = new State(this.getID());
        startState.addTransition('e', rNFA.getStartState());

        // Epsilon transition the rNFA_End to the rNFA_Start
        rNFA.getEndState().addTransition('e', rNFA.getStartState());

        // Create an End state and epsilon transition from rNFA_End to this end state
        State endState = new State(this.getID());
        rNFA.getEndState().addTransition('e', endState);

        NFA plusNFA = new NFA(startState, endState);

        return plusNFA;
    }

    private NFA evalConcat(ASTNode node) throws Exception {
        // Create the rNFA (the NFA that is going to be on left union
        NFA rNFA = this.createNFA(node.getChildren().get(0));

        // Create the sNFA (NFA on right union)
        NFA sNFA = this.createNFA(node.getChildren().get(1));

        // E-transition rNFA_End -> sNFA_Start
        rNFA.getEndState().addTransition('e', sNFA.getStartState());

        NFA concatNFA = new NFA(rNFA.getStartState(), sNFA.getEndState());

        return concatNFA;
    }

    private NFA evalUnion(ASTNode node) throws Exception {

        // Create the rNFA (the NFA that is going to be on left union
        NFA rNFA = this.createNFA(node.getChildren().get(0));

        // Create the sNFA (NFA on right union)
        NFA sNFA = this.createNFA(node.getChildren().get(1));


        // Create a start state and epsilon transition to rNFA_Start and sNFA_Start
        State startState = new State(this.getID());
        startState.addTransition('e', rNFA.getStartState());
        startState.addTransition('e', sNFA.getStartState());

        // Create an End state and epsilon transition from rNFA_End and sNFA_END to this end state
        State endState = new State(this.getID());
        rNFA.getEndState().addTransition('e', endState);
        sNFA.getEndState().addTransition('e', endState);

        NFA unionNFA = new NFA(startState, endState);

        return unionNFA;
    }

    private NFA evalStar(ASTNode node) throws Exception {

        // Create the rNFA (the NFA that is going to be 'stared'
        NFA rNFA = this.createNFA(node.getChildren().get(0));

        // Create a start state and epsilon transition to rNFA_Start
        State startState = new State(this.getID());
        startState.addTransition('e', rNFA.getStartState());

        // Epsilon transition the rNFA_End to the rNFA_Start
        rNFA.getEndState().addTransition('e', rNFA.getStartState());

        // Create an End state and epsilon transition from rNFA_End to this end state
        State endState = new State(this.getID());
        rNFA.getEndState().addTransition('e', endState);

        // Epsilon Transition from this start to this end
        startState.addTransition('e', endState);

        NFA starNFA = new NFA(startState, endState);

        return starNFA;
    }

    /**
     * Return the DFA associated with this evaluator.
     * @param regExAST
     * @return the DFA
     * @throws Exception if the DFA could not be constructed correctly.
     */
    public DFA getDFA(RegExNode regExAST) throws Exception {
        if (this.dfa != null) {
            return this.dfa;
        }

        this.dfa = new DFA();
        // get the Closure of the start state of the NFA.
        Set<State> state1Closure = this.getNFA(regExAST).getStartState().eClosure();

        // Reset State ID counter
        this.nextId = 0;

        // Get the start state
        DFAState startState = new DFAState(this.getID(), state1Closure);
        if (startState.getSubsetStates().contains(this.nfa.getEndState())) {
            startState.setAcceptState(true);
        }

        this.dfa.setStartState(startState);

        // Create List of DFA States and add the start state
        ArrayList<DFAState> Dstates = new ArrayList<DFAState>();
        Dstates.add(startState);

        // Pointer to the current state being looked at.
        DFAState currentState = startState;
        boolean done = false;

        char[] inputSymbols = {'a', 'b', 'c'};

        // Loop until all states in Dstates are marked.
        while (!done) {
            currentState.setMarked(true);

            for (int i = 0; i < inputSymbols.length; i++) {
                ArrayList<State> moveStates = currentState.move(inputSymbols[i]);

                if (moveStates.size() > 0) {
                    Set<State> closureSet = new HashSet<State>();
                    for (State s : moveStates) {
                        closureSet.addAll(s.eClosure());
                    }

                    DFAState newState = new DFAState(0, closureSet);

                    if (!Dstates.contains(newState)) {
                        newState.setId(getID());
                        if (newState.getSubsetStates().contains(this.nfa.getEndState())) {
                            newState.setAcceptState(true);
                        }
                        Dstates.add(newState);
                    } else {
                        newState = Dstates.get(Dstates.indexOf(newState));
                    }

                    currentState.addTransition(inputSymbols[i], newState);
                }
            }

            // See if we are done by checking if all states are marked
            done = true;
            for (DFAState state : Dstates) {
                if (!state.isMarked()) {
                    done = false;
                    currentState = state;
                }
            }
        }

        this.dfa.setNumStates(nextId);

        return this.dfa;
    }

    /**
     * This function will evaluate an expression to determine if it passes the regular expression
     * associated with this evaluator.
     *
     * @param expression the String to evaluate
     * @return true if the expression is accepted by the RegEx, false otherwise.
     */
    public boolean evaluateExpression(String expression) {
        State currentState = this.dfa.getStartState();
        for (int i = 0; i < expression.length(); i++) {
            // traverse the DFA until we reach the end of the input.
            currentState = currentState.evaluateInput(expression.charAt(i));

            // There was no transitions for the input value which means we hit an error state.
            if (currentState == null) {
                return false;
            }
        }

        // If we traversed the DFA till the end of the input and we are on an acceptState, then
        // return true, else return false;
        if (currentState.isAcceptState()) {
            return true;
        } else {
            return false;
        }
    }
}